package Bi_Tree.three_traversal;

import Bi_Tree.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class lc94_no_recursion {
    //迭代法中序遍历二叉树
    /*
    * 入栈向左一直走，出栈访问右子树
    * */
    public static void main(String[] args) {

    }
    public List<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack=new Stack<>();
        List<Integer> list=new ArrayList<>();
        if(root==null){
            return list;
        }
        TreeNode node=root;
        while(node!=null||!stack.isEmpty()){
            if(node!=null){
                stack.push(node);
                node=node.left;
            }else{
                 node=stack.pop();
                 list.add(node.val);
                 node=node.right;
            }
        }
        return list;

    }
}
